class Node {
    constructor(data) {
        this.data = data;
        this.next = null;
    }
}

class LinkedList {
    constructor() {
        this.head = null;
        this.last = null;
        this.size = 0;
    }
    // 插入
    insert(index, data) {
        if (index < 0 || index > this.size) throw new Error('超出链表范围');
        const insertedNode = new Node(data);
        // 插入空
        if (this.size === 0) {
            this.head = insertedNode;
            this.last = insertedNode;
        }
        // 插入头
        if (index === 0) {
            insertedNode.next = this.head;
            this.head = insertedNode;
        }
        // 插入中
        if (index > 0 && index < this.size) {
            const prevNode = this.get(index - 1);
            insertedNode.next = prevNode.next;
            prevNode.next = insertedNode;
        }
        // 插入尾
        if (index === this.size) {
            this.last.next = insertedNode;
            this.last = insertedNode;
        }
        this.size++;
    }
    // 删除
    remove(index) {
        if (index < 0 || index >= this.size) throw new Error('超出链表范围');
        let removedNode = null;
        // 删除头
        if (index === 0) {
            removedNode = this.head;
            this.head = this.head.next;
        }
        // 删除中
        if (index > 0 && index < this.size - 1) {
            const prevNode = this.get(index - 1);
            const nextNode = prevNode.next.next;
            removedNode = prevNode.next;
            prevNode.next = nextNode;
        }
        // 删除尾
        if (index === this.size - 1) {
            const prevNode = this.get(index - 1);
            removedNode = prevNode.next;
            prevNode.next = null;
            this.last = prevNode;
        }
        this.size--;
        return removedNode;
    }
    // 查找
    get(index) {
        if (index < 0 || index > this.size) throw new Error('超出链表范围');
        let temp = this.head;
        for (let i = 0; i < index; i++) {
            temp = temp.next;
        }
        return temp;
    }
    // 更新
    set(index, data) {
        if (index < 0 || index > this.size) throw new Error('超出链表范围');
        const currNode = this.get(index);
        currNode.data = data;
    }
    output() {
        let temp = this.head;
        for (let i = 0; i < this.size; i++) {
            console.log(temp.data);
            temp = temp.next;
        }
    }
}

/* 
{
    head: {
        data: xx,
        next: {
            data: xx,
            next: {

            }
        }
    },
    last: {
        data: xx
        next: null
    },
    size: n
}
*/

const linkedList = new LinkedList();
linkedList.insert(0, 0);
linkedList.insert(1, 1);
linkedList.insert(1, 2);
linkedList.insert(2, 3);
linkedList.insert(3, 4);
linkedList.remove(0);
console.log(linkedList);
// linkedList.output();


const linkedList2 = new LinkedList();
linkedList2.insert(0,3);
linkedList2.insert(0,4);
linkedList2.insert(2,9);
linkedList2.insert(3,5);
linkedList2.insert(1,6);
linkedList2.remove(0);
// console.log(linkedList2);
// linkedList2.output();
